package gold.gold04;

import java.util.Arrays;

/**
 * 用A, B交换的方式也可以避免复杂度上升。
 */
public class S1001合并排序的数组 {
    // 100, 没啥好说的, 空间换时间吧。
    // 想单纯用排序, 所以给A B 后面都塞了一个Integer.MAX_VALUE, 两个都走到max_value的时候也就走完了, 不用循环。了。
    public void merge(int[] A, int m, int[] B, int n) {
        if(n == 0) return;
        int posiA = 0, posiB = 0;

        int[] APlus = new int[m+1];
        if (m >= 0) System.arraycopy(A, 0, APlus, 0, m);
        // 上面这个系统自动优化的System.arraycopy()方法, 是jvm方法, System类中的东西。做题也可以用。
//        for(int i = 0; i < m; i++){
//            APlus[i] = A[i];
//        }
        APlus[m] = Integer.MAX_VALUE;
        int[] BPlus = new int[n+1];
        if (n >= 0) System.arraycopy(B, 0, BPlus, 0, n);
        BPlus[n] = Integer.MAX_VALUE;

        for(int i = 0; i < m + n; i++){
            A[i] = APlus[posiA] > BPlus[posiB] ? BPlus[posiB++] : APlus[posiA++];
        }
    }

    // 先放进去再排序
    public void merge2(int[] A, int m, int[] B, int n) {
        for (int i = 0; i != n; ++i) {
            A[m + i] = B[i];
        }
        Arrays.sort(A);
    }

    // 经典双指针, 这个对于触及边界的处理方式还挺好的。也有一点空间换时间, 创了一个新的数组。
    public void merge3(int[] A, int m, int[] B, int n) {
        int pa = 0, pb = 0;
        int[] sorted = new int[m + n];
        int cur;
        while (pa < m || pb < n) {
            if (pa == m) {
                cur = B[pb++];
            } else if (pb == n) {
                cur = A[pa++];
            } else if (A[pa] < B[pb]) {
                cur = A[pa++];
            } else {
                cur = B[pb++];
            }
            sorted[pa + pb - 1] = cur;
        }
        for (int i = 0; i != m + n; ++i) {
            A[i] = sorted[i];
        }
    }

    // 简洁, 挺好。
    public void merge4(int[] nums1, int m, int[] nums2, int n) {
        int p1=m-1;
        int p2=n-1;
        int cur=m+n-1;
        while (p2>=0){
            nums1[cur--]=(p1>=0&&nums2[p2]<nums1[p1])?nums1[p1--]:nums2[p2--];
        }
    }

}
